package com.fyl.basic_algorithm.linkedList;

import java.util.Scanner;

/**
 * @author 冯永龙
 * @date 2021/3/12 9:53
 */
public class LRUBaseLinkedList<T> {
    private final static Integer DEFAULT_CAPACITY = 10; //默认链表容量

    private SNode<T> headNode; //头结点

    private Integer length; //连表长度

    private Integer capacity;  //链表容量

    public LRUBaseLinkedList() {
        this.headNode = new SNode<T>();
        this.length = 0;
        this.capacity = DEFAULT_CAPACITY;
    }

    public LRUBaseLinkedList(Integer capacity) {
        this.headNode = new SNode<T>();
        this.length = 0;
        this.capacity = capacity;
    }

    public void add(T data) {
        SNode preNode = findPreNode(data);  //先在链表寻找元素，返回其前节点

        if (preNode != null) {
            //删除原始数组在插入到链表头
            deleteElemOptim(preNode);
            insertElemAtBegin(data);
        } else {
            //链表容量不够删除尾节点在插入头部
            if (length >= capacity) {
                deleteElemAtEnd();
            }
            insertElemAtBegin(data);
        }
    }

    /**
     * 找到元素的前一个节点
     *
     * @param data
     * @return
     */
    public SNode findPreNode(T data) {
        SNode sNode = this.headNode;
        for (int i = 0; i < length; i++) {
            if (sNode.getNext().getElement().equals(data)) {
                return sNode;
            }
            sNode = sNode.getNext();
        }
        return null;
    }

    /**
     * 链表头部插入节点
     *
     * @param data
     */
    public void insertElemAtBegin(T data) {
        SNode next = headNode.getNext();
        headNode.setNext(new SNode(data, next));
        length++;
    }

    /**
     * 删除preNode节点后一个元素
     * preNode是元素的前一个节点
     * @param preNode
     */
    public void deleteElemOptim(SNode preNode) {
        SNode next = preNode.getNext();
        preNode.setNext(next.getNext());
        next = null;
        length--;
    }


    /**
     * 删除尾节点
     */
    public void deleteElemAtEnd() {

        SNode ptr = headNode;
        //空链表直接返回
        if (ptr.getNext()==null){
            return;
        }

        //获取倒数第二个节点
        while (ptr.getNext().getNext()!=null){
            ptr = ptr.getNext();
        }

        ptr.setNext(null);
        length--;
    }

    public void printAll(){
        SNode node = headNode.getNext();
        while (node!=null){
            System.out.println(node.getElement()+" ");
            node = node.getNext();
        }

        System.out.println();
    }
}

class testLinkList{
    public static void main(String[] args) {
        LRUBaseLinkedList list = new LRUBaseLinkedList();
        Scanner sc = new Scanner(System.in);

        while (true){
            list.add(sc.next());
            list.printAll();
        }

    }
}

class SNode<T> {

    private T element;

    private SNode next;

    public SNode(T element) {
        this.element = element;
    }

    public SNode(T element, SNode next) {
        this.element = element;
        this.next = next;
    }

    public SNode() {
        this.next = null;
    }

    public T getElement() {
        return element;
    }

    public void setElement(T element) {
        this.element = element;
    }

    public SNode getNext() {
        return next;
    }

    public void setNext(SNode next) {
        this.next = next;
    }
}
